package com.chj.jz.dp.class06;

public class Code01_LongestCommonSubsequence {
	/**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    // 去掉以下所有注释可以打印solution
    public static int longestCommonSubsequence(String AA, String BB) {
        char[] A = AA.toCharArray();
        char[] B = BB.toCharArray();
        int m = A.length;
        int n = B.length;
        int[][] f = new int[m + 1][n + 1];
        int[][] pi = new int[m + 1][n + 1];
        int i, j;
        for (i = 0; i <= m; ++i) {
            for (j = 0; j <= n; ++j) {
                if (i == 0 || j == 0) {
                    f[i][j] = 0;
                    continue;
                }
                
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if (f[i][j] == f[i - 1][j]) {
                    pi[i][j] = 0;
                }
                else {
                    pi[i][j] = 1;
                }

                if (A[i - 1] == B[j - 1]) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                    if (f[i][j] == f[i - 1][j - 1] + 1) {
                        pi[i][j] = 2;
                    }
                }
            }
        }
        
        char[] res = new char[f[m][n]];
        int p = f[m][n] - 1;
        i = m;
        j = n;
        while (i > 0 && j > 0) {
            if (pi[i][j] == 0) {
                --i;
            }
            else if (pi[i][j] == 1) {
                --j;
            }
            else {
                res[p] = A[i - 1];
                --p;
                --i;
                --j;
            }
        }
        
        System.out.println("Longest common subsequence is:");
        for (i = 0; i < f[m][n]; ++i) {
            System.out.print(res[i]);    
        }
        
        System.out.println("");
        
        return f[m][n];
    }
    
    public static void main(String[] args) {
//    	输入:  "ABCD" and "EDCA"
		{
			String str1 = "ABCD";
			String str2 = "EDCA";
			System.out.println(longestCommonSubsequence(str1, str2));
		}
		{
//			输入: "ABCD" and "EACB"
			String str1 = "ABCD";
			String str2 = "EACB";
			System.out.println(longestCommonSubsequence(str1, str2));
		}
		{
//			输入: "ABCD" and "EACB"
			String str1 = "jiuzhang";
			String str2 = "lijiang";
			System.out.println(longestCommonSubsequence(str1, str2));
		}
    }
}
